package demo.letcode._初级算法;

import java.util.ArrayList;
import java.util.List;

public class _字母组合 {
    public static void main(String[] args) {
        /**
         * 题目描述
         * 给定M个字符(-z),从中取出任意字符（每个字符只能用一次）拼接成长度为N的字符串因，要求相同的字符不能相邻。
         * 计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串
         * 则返回0。
         *
         * 输入描述
         * 给定长度为M的字符列表和结果字符串的长度N，,中间使用空格("")拼接。
         * ·0<M<30
         * .0<N≤5
         *
         * 输出描述
         * 输出满足条件的字符串个数。
         *
         * 输入
         * abc 1
         * 输出
         * 3
         * 说明
         * 给的的字符为abc 结果字符串长度为1 拼接成a b c共3种
         *
         * 示例2
         * 输入
         * dde 2
         * 输出
         * 2
         * 说明
         * 给定的字符为dde，结果字符长度为2，拼接成de ed2种
         */
        a();
    }


    public static void a() {
        /**
         * 按顺序输出当前字符和剩余字符的指定个数的全排序组合
         * 输入
         * abcd 2
         * 要求输出从a和bcd，b和cd、c和d的组合
         * 输出
         * [ab, ac, ad, bc, bd, cd]
         *
         * 输入
         * abcd 3
         * 输出
         * [abc, abd, acd, bcd]
         */
        String s = "abcd";
        int n = 2;
        List<String> ret = new ArrayList<>();
        // i和剩余的组合
        for (int j = 0; j < s.length(); j++) {
            def0(s.toCharArray(), n, j + 1, ret, s.charAt(j) + "");
        }

        System.out.println(ret);
    }

    private static void def0(char[] s, int n, int i, List<String> ret, String s1) {
        if (s1.length() == n) {
            ret.add(s1);
            return;
        }
        for (int j = i; j < s.length; j++) { // 从i以后的剩余的字母进行排列
            def0(s, n, j + 1, ret, s1 + s[j]);
        }
    }
}
